﻿#include <iostream>
#include <string>

using namespace std;

#define MIN(a,b) (a<b?a:b)

static string palindromicStringWithLeastAddedCharacters(const char* str)
{
	if (!str) return "";

	auto strLen = strlen(str);
	if (strLen == 0) return "";
	if (strLen == 1) return str;

	int* dp = (int*)malloc(strLen * strLen * sizeof(int));
	memset(dp, 0, strLen * strLen * sizeof(int));

	for (int i = 0; i < strLen; i++)
	{
		dp[i + i * strLen] = 0;
		if (i < strLen - 1)
		{
			dp[i + 1 + i * strLen] = str[i] == str[i + 1] ? 0 : 1;
		}
	}

	int left;
	int down;
	int leftDown;
	for (int i = strLen - 1 - 2; i >= 0; i--)
	{
		for (int j = i + 2; j < strLen; j++)
		{
			left = dp[j - 1 + i * strLen];
			down = dp[j + (i + 1) * strLen];
			leftDown = dp[j - 1 + (i + 1) * strLen];
			if (str[i] == str[j])
			{
				dp[j + i * strLen] = leftDown;
			}
			else
			{
				dp[j + i * strLen] = MIN((left+1),(down+1));
			}
		}
	}

	//for (int i = 0; i < strLen; i++)
	//{
	//	for (int j = 0; j < strLen; j++)
	//	{
	//		printf("%d ", dp[j + i * strLen]);
	//	}

	//	printf("\n");
	//}

	int minCountAdded = dp[strLen - 1];
	char* resStr = (char*)malloc(strLen + minCountAdded + 1);
	memset(resStr, 0, strLen + minCountAdded + 1);
	int l = 0;
	int r = strLen + minCountAdded - 1;
	int i = 0;
	int j = strLen - 1;

	while (i< strLen && j >= 0 && l <= r)
	{
		if (i == j)
		{
			resStr[l++] = str[i];
		}
		else if (str[i] == str[j])
		{
			// 取左下
			resStr[l++] = str[i++];
			resStr[r--] = str[j--];
		}
		else if (dp[j + i * strLen] == dp[j - 1 + i * strLen] + 1)
		{
			// 取左
			resStr[l++] = str[j];
			resStr[r--] = str[j];
			--j;
		}
		else
		{
			// 取下
			resStr[l++] = str[i];
			resStr[r--] = str[i];
			++i;
		}
	}

	free(dp);
	string resString = resStr;
	free(resStr);
	return resString;
}

/**
 * 给定一个字符串str，如果可以在str的任意位置添加字符，请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。
 * 
 * 举例：
 * str="ABA", str本身就是回文串，不需要添加字符，所以返回"ABA".
 * str="AB", 可以在'A'之前添加'B', 使str整体都是回文串，故可以返回"BAB"；也可以在'B'之后添加'A', 使str整体都是回文串，故也可以返回"ABA". 总之，只要添加的字符数最少，返回其中一种结果即可。
 * 
 * 思路：
 * 先使用动态规划的范围尝试方法，列出dp表，得到添加的最少字符的个数，再根据dp表反推最终的整个字符串。
 * 范围尝试：str从i位置到j位置添加的最少字符是多少个?
 * 
 * 举例:
 * str="a12bc321"	
 * 
 *           a   1   2   b   c   3   2   1
 *           0   1   2   3   4   5   6   7   j
 *    ---------------------------------------------
 *    a   0| 0	 1	 2	 3	 4	 5	 4	 3
 *    1   1| X	 0	 1	 2	 3	 4	 3	 2
 *    2   2| X	 X	 0	 1	 2	 3	 2	 3
 *    b   3| X	 X	 X	 0	 1	 2	 3	 4
 *    c   4| X	 X	 X	 X	 0	 1	 2	 3
 *    3   5| X	 X	 X	 X	 X	 0	 1	 2
 *    2   6| X	 X	 X	 X	 X	 X	 0	 1
 *    1   7| X	 X	 X	 X	 X	 X	 X	 0
 *        i|
 * 
 * ∵i≤j，∴从(0,0)开始的斜45°分界线下面的元素无意义; 斜45°分界线本身的元素，i==j，只有一个字符，故都填0。
 * 对于(0,1),(1,2),(2,3),...,(6,7), 如果str[i]==str[i+1]，则填0，否则填1.
 * 
 * 对于普遍位置(i,j), 有3种可能
 * 1. 将str[i]单独拿出，只要i+1~j凑出回文，那么只要在j后追加一个str[i]，即可凑出回文, dp(i+1,j)+1
 * 2. 将str[j]单独拿出，只要i~j-1凑出回文，那么只要在i前追加一个str[j], 即可凑出回文, dp(i,j-1)+1
 * 3. 当且仅当str[i]==str[j]时，只要i+1~j-1凑出回文，那么i~j必然是回文, dp(i+1,j-1)
 * 由此可以看出，dp(i,j)的值由它左边，下边和左下的值可以得出。
 * 这张dp表，应该按照由下到上，同一行由左到右的顺序推导出。
 * 
 * 最终，推导出(0,7)的值是3, 然后反向推导出增加的字符。
 * 
 * 先声明好一个长度为8+3的空的char数组arr。 arr=['','','','','','','','','','','',]
 * (0,7)是由下方的格子(1,7)+1得到的，即(1,7)的格子，保留了str[0],并在最后追加了str[0], 故arr最左填str[0], 最右填str[0], ∴arr[0]=str[0], arr[10]=str[0].
 * (1,7)是由(2,6)得到的，保留了str[1],str[7], 故arr最左填str[1], 最右填str[7], ∴arr[1]=str[1], arr[9]=str[7].
 * (2,6)是由(3,5)得到的, 保留了str[2],str[6]，故arr最左填str[2], 最右填str[6]，∴arr[2]=str[2],arr[8]=str[6]
 * (3,5)可以由(3,4)或(4,5)得到，两条路线效果是等价的，故任意选一条路线。(3,4), 保留了str[5], 并在前面追加了str[5], 故arr最左填str[5], 最右填str[5], ∴arr[3]=str[5], arr[7]=str[5].
 * (3,4)可以由(3,3)或(4,4)得到，两条路线效果是等价的，故任意选一条路线。(3,3), 保留了str[4], 并在前面追加了str[4], 故arr最左填str[4], 最右填str[4], ∴arr[4]=str[4], arr[6]=str[4].
 * (3,3)只剩下一个字符str[3], 故arr[5]=str[3].
 * 
 * 综上，arr即为所求：
 * arr=['a','1','2','3','c','b','c','3','2','1','a',]
 * 
 * 反推的过程，其实就是根据dp表，将arr从左右两端逐步往中间填写的过程。
 */
int main_makePalindromicStringByAddingCharacters()
{
	char str[] = "abc1ddef";
	auto res = palindromicStringWithLeastAddedCharacters(str);
	printf("%s\n%s", str, res.c_str());
	return 0;
}